import java.util.Scanner;

public class Test4 {
    //01背包问题——一维数组优化
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        //从键盘中读取n，V和v数组、w数组
        int n = s.nextInt(), V = s.nextInt();
        int[] v = new int[n + 1], w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = s.nextInt();
            w[i] = s.nextInt();
        }
        //确定状态表示为dp[i][j]为从前i个位置（包括i）位置的物品中选择物品装入背包容积
        //为j时的背包中价值最大的值
        //创建dp表
        int[] dp = new int[V + 1];
        //初始化：因为数组中的默认值是0，所以这里不需要进行其他的操作
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = V; j >= v[i]; j--) {
                //第i个位置的物品不选择的情况一定存在,所以我们先处理不选择的请跨国
                //再来判断第i个位置的物品是否可以装入背包,取两种情况的最大值
                dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        //确定返回值，返回的是在n个物品中选择物品装入背包容量为V的背包中物品的最大价值，
        //所以返回的值为dp[n][V]
        System.out.println(dp[V]);

        //状态表示为dp[i][j]为从前i个位置的物品中选择物品装入背包容积为j并且背包恰好装满
        //时候的背包中物品总价值的最大值

        //初始化
        //因为前面使用了dp，我们可以再创建一个表，也可以对dp表进行修改
        for (int i = 1; i <= V; i++) dp[i] = -1;
        //填表
        for (int i = 1; i <= n; i++) {
            //当j < v[i]的时候背包就装不下第i个物品了，所以前面的j也就不需要遍历了
            for (int j = V; j >= v[i]; j--) {
                if (dp[j - v[i]] != -1) dp[j] = Math.max(dp[j],dp[j - v[i]] + w[i]);
            }
        }
        //确定返回值，因为题目中要的是从n个物品中选择物品装入背包容积为V并且背包恰好装满
        //时候的背包中的物品的最大价值，所以返回值为dp[n][V]，并且题目中说了如果不存在
        //背包恰好装满的情况就返回0
        System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}
